#define _CRT_SECURE_NO_WARNINGS

//Problem 1:
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
//class Solution {
//public:
//    TreeNode* invertTree(TreeNode* root) {
//        queue<TreeNode*> que;
//        if (root != NULL)
//            que.push(root);
//        while (!que.empty()) {
//            int size = que.size();
//            for (int i = 0; i < size; i++) {
//                TreeNode* node = que.front();
//                que.pop();
//                swap(node->left, node->right);
//                if (node->left) que.push(node->left);
//                if (node->right) que.push(node->right);
//            }
//        }
//        return root;
//    }
//};

//class Solution {
//public:
//    TreeNode* invertTree(TreeNode* root) {
//        if (root == NULL)
//            return NULL;
//        swap(root->left, root->right);
//        invertTree(root->left);
//        invertTree(root->right);
//        return root;
//    }
//};

//Problem 2:
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
//class Solution {
//public:
//    bool isSymmetric(TreeNode* root) {
//        return isSymmetricTree(root->left, root->right);
//    }
//
//    bool isSymmetricTree(TreeNode* Tleft, TreeNode* Tright) {
//        if (Tleft == NULL && Tright == NULL)
//            return true;
//        if (Tleft == NULL || Tright == NULL || Tleft->val != Tright->val)
//            return false;
//        return isSymmetricTree(Tleft->left, Tright->right) && isSymmetricTree(Tleft->right, Tright->left);
//    }
//};

//Problem 3:
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
//class Solution {
//public:
//    bool isSameTree(TreeNode* TreeLeft, TreeNode* TreeRight) {
//        if (TreeLeft == NULL && TreeRight == NULL)
//            return true;
//        if (TreeLeft == NULL || TreeRight == NULL)
//            return false;
//        if (TreeLeft->val != TreeRight->val)
//            return false;
//
//        return isSameTree(TreeLeft->left, TreeRight->left) && isSameTree(TreeLeft->right, TreeRight->right);
//    }
//
//    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
//        if (root == NULL)
//            return false;
//        if (isSameTree(root, subRoot))
//            return true;
//        return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
//    }
//};

//Problem 4:
//#include <stdio.h>
//#include <stdlib.h>
//
//typedef struct TreeNode {
//    char val;
//    struct TreeNode* left;
//    struct TreeNode* right;
//}TreeNode;
//
//TreeNode* CreateTree(char* str, int* pi)
//{
//    if (str[*pi] == '#') {
//        (*pi)++;
//        return NULL;
//    }
//
//    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
//    root->val = str[(*pi)++];
//    root->left = CreateTree(str, pi);
//    root->right = CreateTree(str, pi);
//
//    return root;
//}
//
//void InOrder(TreeNode* root)
//{
//    if (root == NULL)
//        return;
//    InOrder(root->left);
//    printf("%c ", root->val);
//    InOrder(root->right);
//}
//
//int main()
//{
//    char str[101];
//    scanf("%s", str);
//    int i = 0;
//    TreeNode* root = CreateTree(str, &i);
//    InOrder(root);
//
//    return 0;
//}
//#include<stdio.h>
//#include<stdbool.h>
//#include<stdlib.h>
//
//typedef struct TreeNode
//{
//    struct TreeNode* left;
//    struct TreeNode* right;
//    int val;
//}TreeNode;
//
//int isDepth(TreeNode* root) {
//    if (root == NULL) {
//        return 0;
//    }
//    int LeftDepth = isDepth(root->left);
//    int RightDepth = isDepth(root->right);
//
//    return LeftDepth > RightDepth ? LeftDepth + 1 : RightDepth + 1;
//}
//
//bool isBalanced(TreeNode* root) {
//    if (root == NULL)
//        return true;
//    if (abs(isDepth(root->left) - isDepth(root->right)) > 1)
//        return false;
//
//    return isBalanced(root->left) && isBalanced(root->right);
//}
//
//TreeNode* CreateTreeNode(int val)
//{
//    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
//    if (node == NULL) {
//        exit(-1);
//    }
//
//    node->val = val;
//    node->left = NULL;
//    node->right = NULL;
//
//    return node;
//}
//
//int main()
//{
//    TreeNode* n1 = CreateTreeNode(1);
//    TreeNode* n2 = CreateTreeNode(2);
//    TreeNode* n3 = CreateTreeNode(2);
//    TreeNode* n4 = CreateTreeNode(3);
//    TreeNode* n5 = CreateTreeNode(3);
//    n1->left = n2;
//    n1->right = n3;
//    n2->left = n4;
//    n3->right = n5;
//
//    bool res = isBalanced(n1);
//    printf("%d\n", res);
//
//    return 0;
//}
